322. 零钱兑换

Similar Question

Solution Tips

方案一: 完全背包

var coinChange = function(coins, amount) {
    // 完全背包, 求的是最少的硬币个数. 而不是组合总数
    // 那就是要选择物品了?
    // 我目前会求的是最大价值和组合总数
    // 从最大价值的方案里, 贪心一下?
    // 如果是 dp[i][j], 那就是总数为 j 时, 从 [0 - i] 的物品中选择, 价值最大是多少
    // 好像反过来处理一下就可以了? dp[11] = dp[11 - 5] + 5 = dp[6 - 5] + 5 + 5 = dp[1] = 1 + 5 + 5
    // 与 dp[j] 对应的选择硬币数量最少的方案
    const dp = Array.from({ length: amount + 1}).fill(100000);
    dp[0] = 0;
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            // 选的太贪婪了, 漏了方案, 不一定要全选 coins[i] 的
            // 即是排序了也不能贪婪
            // dp[j] = Math.min(dp[j], dp[rest] + count);
            // 考虑到有 [1,7,10] 这种用例，按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到
            dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j]);
        }
    }

    return dp[amount] === 100000 ? -1 : dp[amount];
};

let coins = [186,419,83,408], amount = 6249
console.log(coinChange(coins, amount));